import MySecurity.*;

class MySecurity.Barrett{
	public var modulus:BigInt;
	public var k:Number;
	public var mu:BigInt;
	public var bkplus1:BigInt;
	
	public function Barrett(m:BigInt)
	{
		this.modulus = BigInt.biCopy(m);
		this.k = BigInt.biHighIndex(this.modulus) + 1;
		var b2k = new BigInt();
		b2k.digits[2 * this.k] = 1; 
		this.mu = BigInt.biDivide(b2k, this.modulus);
		this.bkplus1 = new BigInt();
		this.bkplus1.digits[this.k + 1] = 1; // bkplus1 = b^(k+1)
	}
	public function modulo(x:BigInt):BigInt
	{
		var q1:BigInt = BigInt.biDivideByRadixPower(x, this.k - 1);
		var q2:BigInt = BigInt.biMultiply(q1, this.mu);
		var q3:BigInt = BigInt.biDivideByRadixPower(q2, this.k + 1);
		var r1:BigInt = BigInt.biModuloByRadixPower(x, this.k + 1);
		var r2term:BigInt = BigInt.biMultiply(q3, this.modulus);
		var r2:BigInt = BigInt.biModuloByRadixPower(r2term, this.k + 1);
		var r:BigInt = BigInt.biSubtract(r1, r2);
		if (r.isNeg) {
			r = BigInt.biAdd(r, this.bkplus1);
		}
		var rgtem:Boolean = BigInt.biCompare(r, this.modulus) >= 0;
		while (rgtem) {
			r = BigInt.biSubtract(r, this.modulus);
			rgtem = BigInt.biCompare(r, this.modulus) >= 0;
		}
		return r;
	}
	public function multiplyMod(x:BigInt, y:BigInt):BigInt
	{
		var xy:BigInt = BigInt.biMultiply(x, y);
		return this.modulo(xy);
	}
	
	
	public function powMod(x:BigInt, y:BigInt):BigInt
	{
		var result:BigInt = new BigInt();
		result.digits[0] = 1;
		var a:BigInt = x;
		var k:BigInt = y;
		while (true) {
			if ((k.digits[0] & 1) != 0) result = this.multiplyMod(result, a);
			k = BigInt.biShiftRight(k, 1);
			if (k.digits[0] == 0 && BigInt.biHighIndex(k) == 0) break;
			a = this.multiplyMod(a, a);
		}
		return result;
	}
}